package com.lsa.edmonds.chap5;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Collections;
import com.lsa.helpers.Utils;

import com.lsa.helpers.IntArrayListAdapter;
import com.lsa.shenn.common.Sorter;

public class BucketSort implements Sorter
{
	private static int BUCKET_COUNT = 5;
	private static int SIMPLE_SORT_SIZE = 3;
	
	public int[] sort(int[] array)
	{
		List<Integer> list = new IntArrayListAdapter(array);
		list = sort(list);
		return Utils.toPrimitiveArray(list);
	}
	
	public List<Integer> sort(List<Integer> array)
	{
		List<Integer> sortedList = new ArrayList<Integer>();  
		Stack<Bucket> bucketsStack = new Stack<Bucket>();
		bucketsStack.add(new Bucket(array));
		innnerSort(sortedList, bucketsStack);
		
		return sortedList;
	}
	
	void innnerSort(List<Integer> sortedList, Stack<Bucket> bucketsStack)
	{
		while(!bucketsStack.isEmpty())
		{
			Bucket currentBucket = bucketsStack.pop();
			if (currentBucket.size() <= SIMPLE_SORT_SIZE)
			{
				currentBucket.simpleSort();
				sortedList.addAll(currentBucket.getData());
			}
			else
			{
				List<Bucket> newBuckets = currentBucket.split(BUCKET_COUNT);
				for (int i = newBuckets.size() - 1; i > -1; --i)
				{
					bucketsStack.push(newBuckets.get(i));
				}
			}
		}
	}
	
	private class Bucket
	{
		private double min;
		private double max;
		
		private List<Integer> data = new ArrayList<Integer>();
		
		public Bucket(List<Integer> data)
		{
			this.data = data;
			if (!data.isEmpty())
			{
				this.min = Collections.min(data);
				this.max = Collections.max(data);
			}
		}
		
		@Override
		public String toString() {
			return "Bucket [min=" + min + ", max=" + max + ", data=" + data
					+ "]";
		}

		public void setMin(double min)
		{
			this.min = min;
		}

		public void setMax(double max)
		{
			this.max = max;
		}

		public Bucket(double min, double max)
		{
			this.min = min;
			this.max = max;
		}

		public void add(Integer n)
		{
			this.data.add(n);
		}
		
		Integer get(int i )
		{
			return this.data.get(i);
		}

		public List<Integer> getData()
		{
			return this.data;
		}

		public int size()
		{
			return this.data.size();
		}
		
		public void simpleSort()
		{
			Collections.sort(this.data);
		}
		
		public List<Bucket> split(int bucketCount)
		{
			double h = (this.max -this.min) / bucketCount;
			
			List<Bucket> bucketList = new ArrayList<Bucket>();
			
			for (int i = 0; i < bucketCount - 1; i++)
			{				
				double newMin = this.min + i * h;
				double newMax = this.min + (i + 1) * h;
				Bucket bucket = new Bucket(newMin, newMax);
				bucketList.add(bucket);
			}			
			
			{
				int i = bucketCount - 1;
				double newMin = this.min + i * h;
				double newMax = this.max;
				Bucket bucket = new Bucket(newMin, newMax);
				bucketList.add(bucket);
			}
			
			for (int i = 0; i < this.size(); i++)
			{
				Integer n = this.get(i);
				
				int index = getBucketIndex(this.min, h, bucketCount, n);
				Bucket bucket = bucketList.get(index);
				bucket.add(n);
			}
			
			return bucketList;
		}
		
		public int getBucketIndex(double min, double h, int bucketCount, Integer n)
		{
			int bucketIndex = (int)((n.doubleValue() - min) / h);
			if (bucketIndex > bucketCount - 1)
			{
				bucketIndex = bucketCount - 1;
			}
			
			return bucketIndex;
		}
	}
}
